package 数据结构与算法.排序算法;

import java.time.LocalDateTime;
import java.util.Arrays;

public class ShellSort {
    public static void main(String[] args) {
        int[] arr={8,9,1,7,2,3,5,4,6,0};
        shellSort2(arr);

//        int[] arr = new int[80000];
//        for (int i = 0; i < arr.length; i++) {
//            arr[i] = (int) (Math.random() * 8000000);
//        }
//
//        System.out.println("排序前的时间："+ LocalDateTime.now());
//
//        shellSort2(arr);
//
//        System.out.println("排序后的时间："+ LocalDateTime.now());

    }

    //交换法
    public static void shellSort(int[] arr) {
        int temp = 0;
        int count = 0;
        for (int gap = arr.length / 2; gap > 0; gap /= 2) {
            for (int i = gap; i < arr.length; i++) {
                //遍历各组中所有元素，步长为5
                for (int j = i - gap; j >= 0; j -= gap) {
                    //如果当前元素大于加上步长后的那个元素，说明交换
                    if (arr[j] > arr[j + gap]) {
                        temp = arr[j];
                        arr[j] = arr[j + gap];
                        arr[j + gap] = temp;
                    }
                }
            }
//            System.out.println("希尔排序第"+(++count)+"轮="+ Arrays.toString(arr));
        }
    }

    //移位法
    public static void shellSort2(int[] arr){
        int count=0;
        for (int gap=arr.length/2;gap>0;gap/=2){
            for (int i = gap; i < arr.length; i++) {
                int j=i;
                int temp=arr[j];
                if (arr[j]<arr[j-gap]){
                    while(j-gap>=0&&temp<arr[j-gap]){
                        //移动
                        arr[j]=arr[j-gap];
                        j-=gap;
                    }
                      //当退出while后，就给temp找到插入位置
                    arr[j]=temp;
                }
            }
            System.out.println("希尔排序第"+(++count)+"轮="+ Arrays.toString(arr));
        }
    }

//        int temp=0;
//        //希尔排序第一轮
//        for (int i = 5; i < arr.length; i++) {
//            //遍历各组中所有元素，步长为5
//            for (int j = i-5; j >= 0; j-=5) {
//                //如果当前元素大于加上步长后的那个元素，说明交换
//                if (arr[j]>arr[j+5]){
//                    temp=arr[j];
//                    arr[j]=arr[j+5];
//                    arr[j+5]=temp;
//                }
//            }
//        }
}
